- strongly connected components
- сильно связанные компоненты
English-Russian electronics dictionary .
strongly connected components
Смотреть что такое "strongly connected components" в других словарях:
Tarjan's strongly connected components algorithm — Tarjan s Algorithm (named for its discoverer, Robert Tarjan) is a graph theory algorithm for finding the strongly connected components of a graph. It can be seen as an improved version of Kosaraju s algorithm, and is comparable in efficiency to… … Wikipedia
Strongly connected component — Graph with strongly connected components marked A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a … Wikipedia
Connected component (graph theory) — A graph with three connected components. In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example,… … Wikipedia
2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… … Wikipedia
Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… … Wikipedia
Kosaraju's algorithm — In computer science, Kosaraju s algorithm is an algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju. It makes use of the fact that the… … Wikipedia
Depth-first search — Order in which the nodes are visited Class Search algorithm Data structure Graph Worst case performance … Wikipedia
Null graph — In the mathematical field of graph theory, the null graph may refer either to the order zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an empty graph). Contents 1 Order zero graph 2 Edgeless graph 3 See also … Wikipedia
Robert Tarjan — Infobox Scientist name = Robert Endre Tarjan image width = caption = birth date = Birth date and age|1948|4|30|mf=y birth place = Pomona, California death date = death place = residence = citizenship = nationality = ethnicity = field = Computer… … Wikipedia
Closure problem — A Closure problem is a problem in graph theory for finding a set of vertices in a directed graph such that there are no edges from the set to the rest of the graph. More specifically, the minimum closure problem asks for a set of this type with… … Wikipedia
Cycle rank — In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi (Eggan 1963). Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a … Wikipedia
